package temp.leetcode.editor.cn;

//给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。 
//
// 完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。 
//
// 不能使用任何内置的库函数，如 sqrt 。 
//
// 
//
// 示例 1： 
//
// 
//输入：num = 16
//输出：true
//解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
// 
//
// 示例 2： 
//
// 
//输入：num = 14
//输出：false
//解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= num <= 2³¹ - 1 
// 
//
// Related Topics 数学 二分查找 👍 469 👎 0

/**
 * 有效的完全平方数
 *
 * @author saint
 */
class P367_ValidPerfectSquare{
    public static void main(String[] args) {
        Solution solution = new P367_ValidPerfectSquare().new Solution();
        System.out.println("Integer.MAX_VALUE = " + Integer.MAX_VALUE);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isPerfectSquare(int num) {
        if(num ==1){
            return true;
        }
        //找平方根，再判断平方根平方后是否为原来的数
        int low=1,high=num/2;
        int sqrt=1;
        while(low<=high){
            int mid=(low+high)>>1;
            if(mid>num/mid){
                high = mid-1;
            }
            else{
                low=mid+1;
                sqrt=mid;
            }
        }
        if(sqrt*sqrt==num){
            return true;
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
